#include<stdlib.h>
/**
 * 两个子数组的下标分别是
 * 1到m和m+1 到m+n，两端都包括
 * 
 * 方法1，使用插入排序O(m*n) 和 O(1)
 * 方法2，使用归并排序O(m+n) 和 O(m+n)
 * 下面使用归并排序实现
 * 
 * 有没有o(m+n) 和 O(1)的算法，即在原数组内遍历一遍就能完成的？
 */
void sort(int arr[],int m,int n){
    int i=1;
    int j=m+1;
    int k=1;
    int *res=(int*)malloc(sizeof(int)*(m+n+1));
    //两个指针齐头并进
    while (i<=m&&j<=m+n)
    {
        if(arr[i]<=arr[j]){//如果[i]本来就比较小，那么就直接移动
            res[k++]=arr[i++];
        }else{//如果[j]比较小，那么就将i，j交换
            res[k++]=arr[j++];
        }
    }
    //当循环结束的时候
    while (i<=m)
    {
        res[k++]=arr[i++];
    }
    while (j<=m+n)
    {   
        res[k++]=arr[j++];
    }
    
    for(int index=1;index<=m+n;index++){
        arr[index]=res[index];
    }
    
    return ;
}

